%% DIAPO 1
\subsection{Le LSM-Tree}
\begin{frame}[shrink]\frametitle{LSM-Tree} 
	\begin{block}{Présentation}
		\begin{itemize}
			\item structure de données hybride
			\item avantages : insertion indexée rapide
			\item inconvénients : requêtes plus longues
			\item utilité : données de taille importante, requêtes parallélisées
			\item applications : SGBD (LevelDB, Apache Cassandra)
		\end{itemize}
	\end{block}

	\begin{figure}[htb]
		\begin{center}
			\includegraphics[width=\textwidth]{images/lsm_structure.png}
			\caption*{\tiny{(source : The log-structured merge-tree (LSM-tree)-P. O’Neil, E. Cheng, D. Gawlick, E. O’Neil.)}}
		\end{center}
	\end{figure}	
\end{frame}


% DIAPO 2
%~ \subsection{Algorithme de merge}
%~ \begin{frame}\frametitle{Le Rolling Merge}
	%~ \begin{columns}[T]
	 	%~ \begin{column}{.5\textwidth}
	 		%~ \begin{center}
	 			%~ \includegraphics[width=\textwidth]{images/lsm_rolling_merge.png}
	 		%~ \end{center}
	 	%~ \end{column}
	 	%~ \begin{column}{.5\textwidth}
	 		%~ \begin{block}{Fonctionnement}
	 			%~ \begin{itemize}
	 				%~ \item Taille C0 atteint un seuil
	 				%~ \item Création d'un nouveau noeud par fusion avec données C1
	 				%~ \item Recopie vers le disque
	 				%~ \item Suppression de l'ancien noeud de C1
	 			%~ \end{itemize}
	 		%~ \end{block}
	 	%~ \end{column}
	%~ \end{columns}
%~ \end{frame}


%% DIAPO 3
\subsection{Les Limites}
\begin{frame}\frametitle{La Compaction} 
	\begin{columns}[T]
	 	\begin{column}{.5\textwidth}	 		
			\begin{figure}[htb]
				\begin{center}
					\includegraphics[width=\textwidth]{images/lsm_tree_compaction.png}
					\caption*{\tiny{(source : Building Workload-Independant Storage with VT-Trees)}}
				\end{center}
			\end{figure}				
	 	\end{column}
	 	\begin{column}{.5\textwidth}
	 		\begin{block}{Fonctionnement}
	 			\begin{itemize}
	 				\item Mémoire : Memtable
					\item Disque : SSTable = Liste + SI + BF
	 			\end{itemize}
	 		\end{block}
	 	\end{column}
	\end{columns}
	\begin{alertblock}{Point faible}
	Recopie des données de la mémoire vers le disque, puis à chaque compaction. \\
	$log_2$(n) recopies
	\end{alertblock}
\end{frame}
